画像およびビデオのコンテンツアウェアリサイジング

专利摘要:
方法は、まず格子グラフを構築することによって入力画像をサイズ変更する。格子グラフは、入力画像内の画素毎に１つのノードを含み、格子グラフ内の隣接するノードは、アークによって連結される。各アークは有向であり、関連付けられるコストを有する。コスト関数を使用して格子グラフのアークに切断を適用する。シーム内の画素の座標が単調性制約条件および連結性制約条件を施行するように、切断から画素のシームを決定する。次に、入力画像と比較されるときの、出力画像内のエネルギー変化を最小にしながら、シームに従って入力画像をサイズ変更して出力画像を生成する。
公开号:JP2011505631A
申请号:JP2010536051
申请日:2008-11-12
公开日:2011-02-24
发明作者:アビダン、シュミュエル；シャミル、アリエル；ブランド、マッシュー・イー；ルビンスタイン、マイケル
申请人:ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド；
IPC主号:G06T11-20

专利说明:

[0001] 本発明は、包括的には画像処理に関し、より詳細には画像およびビデオをサイズ変更することに関する。]
[0002] ［関連出願］
本出願は、２００７年１１月２９日付けで出願された、米国仮特許出願第６０／９９０，９６４号「Retargeting Images Using Graph Cuts」、および、２００７年１１月３０日付けで出願された、米国仮特許出願第６０／９９１，３６１号「Seam Carving for Content-Aware Video Resizing」に対して優先権を主張し、これらの仮特許出願の双方が、参照によりそれらの全体が援用される。]
背景技術

[0003] シームカービングは、コンテンツを意識した画像サイズ変更のための効果的な技法である。画像を、異なる縦横比または異なる解像度を有する表示装置のためにサイズ変更する必要がある場合がある。同様にして、ビデオを、該ビデオの縦横比、解像度、期間の任意の組み合わせを変更することによって、テレビ、コンピュータ端末、セルラ電話、および他の携帯表示装置のためにサイズ変更することが可能でなくてはならない。]
[0004] シームカービングのビデオへの単純な拡張は、各ビデオフレームを画像として扱い、各フレームを他のフレームから独立してサイズ変更することである。しかしながら、これによって、時間的一貫性がないことに起因するジッタによるアーチファクトが生じる。]
[0005] 従来のシームカービングは、他の制限も有する。顕著な空間構造が現れる画像において、シームカービングは、厄介なアーチファクトを生成し得る。これらのアーチファクトは、空間アーチファクトが時間アーチファクトによって増幅および増大され得るビデオにおいて、より大きなものとなる。実際、人間の目は、動きに対して高感度であるため、人間の知覚の働き方に起因して、時間アーチファクトは、ビデオにおいて、より一層邪魔なものとなる場合がある。]
[0006] 画像およびビデオのサイズ変更に関して、多数の方法および技法が既知である。画像およびビデオ内の対象領域（ＲＯＩ）を検出するために、人間の時空間知覚に基づく注意モデルが使用されてきた。そして、ＲＯＩは、表示サイズがビデオ（または画像）サイズよりも小さい装置上で使用される表示パスを画定するために使用される。ビデオの最も重要度が低いコンテンツは、クロッピングされ、重要な特徴は、より大きなスケールに残され、実質的にズームインのような効果が生じる。]
[0007] 視覚的に快い方式でコンテンツを提示するために、仮想カメラの動きまたは擬似ズームイン／ズームアウト効果が使用されてきた。同様に、ワイドスクリーンの長編映画およびＤＶＤを標準のテレビフォーマットに適合させるプロセスを模倣するために、仮想カメラの動きとともに、クロッピングおよびスケーリングの双方が使用されてきた。１つのシステムは、画像内のオブジェクト、および検出されるオブジェクト、たとえば顔に基づいて情報損失を最小にする。しかしながら、クロッピングは、大量の情報を廃棄し、たとえば、重要な特徴がビデオフレームのエッジ付近に位置する場合（これは、２人の役者間の対話を撮影するために通常行われるようなワイドショットまたは肩越しショットにおいて一般的である）に問題となり得る。]
[0008] 代替的な手法は、画像を背景レイヤおよび前景レイヤに区分けし、各レイヤを独立してスケーリングする。次に、それらのレイヤを再結合して、サイズ変更された画像を生成する。この技法は、区分けの品質に決定的に依存するが、区分けは、それ自体、困難で複雑なタスクである。]
[0009] 別の方法は、オブジェクトべースである。入力ビデオを、複数のオブジェクトおよび複数の動作に区分けする。次に、区分けされたオブジェクトから短いビデオ概要を構成することができる。この方法は、ビデオのリタイミングしか扱わず、ビデオの空間広がりを変更しない。]
[0010] 別の方法は、不均一な大域ワーピングを使用し、空間エッジ、顔検出、および動き検出を含む、ビデオに関する効果的な顕著性マップを定義することに的を絞っている。]
[0011] 代替的な手法は、２Ｄ多様体を、新たなビデオシーケンス内のフレームにマッピングする。進化時間フロント（Evolving Time Fronts）と呼ばれるこの手法によって、動的ビデオシーンにおいて時間を操作することが可能になる。]
[0012] グラフ分割およびグラフベースのコスト最小化技法は、画像復元、画像区分け、オブジェクト認識、および形状再構築のような、画像処理用途およびビデオ処理用途において、広く使用されている。画像を表すグラフは、類似度測定および制約条件に基づいて、２つの別個のサブセットに分割される。１つの方法は、グラフ切断を使用して、２Ｄテクスチャまたは３Ｄテクスチャを画像内にパッチする。]
[0013] 本発明の実施の形態は、コンテンツを意識して画像およびビデオをサイズ変更するための方法およびシステムを提供する。本方法は、２Ｄ画像に対し、１Ｄ画素シームを除去または挿入し、ビデオのような３Ｄ時空間ボリュームに対し、２Ｄ多様体を除去または挿入する。]
[0014] 本発明は、３Ｄボリュームに適したグラフ切断を使用する。格子グラフにおいて、入力画像内の画素を表すノードは、有向アークによって連結される。この定式化において、シームは、格子グラフ内のアークに対する、結果としてのシーム内の画素が単調であり、かつ連結された、すなわち、直接隣接しているような切断によって画定される。]
[0015] さらに、本発明は、サイズ変更された画像およびビデオの視覚的品質（見栄え）を改良するエネルギー関数を提供する。本発明は、前方エネルギーを使用し、入力画像にシームを適用して、入力画像と比較した出力画像におけるエネルギー変化（ΔＥ）が最小になるように、出力画像を生成する。]
[0016] この判断基準は、以下のように表すことができる。]
[0017] ]
[0018] ただし、Ｅはエネルギー関数、たとえば画素単位の濃度差であり、ＩＩは入力画像であり、ＩＯは出力画像であり、Ｃｉは関連付けられるコストを有する画素のシームである。]
発明の効果

[0019] 本発明では、画像およびビデオをサイズ変更するための、改良型シームカービング演算を提供する。ビデオのサイズ変更は、グラフ切断を使用して達成される。本発明では、入力画像ではなく、出力画像に対するシームカービングの効果を測定する前進的なエネルギー関数も提供する。]
[0020] 本発明によるエネルギー測定を、グラフ切断または動的プログラミングのいずれかによって使用することができる。１つの方法は、ビデオを時間的にサイズ変更するようになっていることもできる。ビデオボリュームをＹ×Ｔビューに回転することによって、時間領域を通って切断するシーム多様体を見つけることができる。これらの多様体は、除去されると、ビデオの長さを減少させる。]
図面の簡単な説明

[0021] 本発明の１つの実施の形態による、コンテンツを意識して画像をサイズ変更するための方法のフロー図である。
異なる複数の格子グラフ構築に関するシームを含む、入力画像例である。
図２のシームに関する画像分割および対応する格子グラフのブロック図である。
図２のシームに関する画像分割および対応する格子グラフのブロック図である。
図２のシームに関する画像分割および対応する格子グラフのブロック図である。
図２のシームに関する画像分割および対応する格子グラフのブロック図である。
本発明の実施の形態による格子グラフのブロック図である。
本発明の実施の形態によるグラフ切断の概略図である。
時空間ビデオボリューム、および２Ｄ多様体を形成するシームのブロック図である。
除去されるシームの関数としての出力画像におけるエネルギー変化のグラフである。
垂直シームのための３つの可能な方向を示す図である。
ある入力画像に関して、従来技術の出力画像を、本発明の１つの実施の形態による、入力画像から得られる出力画像と比較する図である。
従来技術のシームを有する画像、および本発明の１つの実施の形態によるシームを有する画像を示す図である。
図９（Ａ）（Ｂ）に対応するエネルギー画像を示す図である。] 図２ 図９
実施例

[0022] 本発明の実施の形態は、グラフ切断から得られる画素のシームを使用して、画像およびビデオをサイズ変更するための方法を提供する。本明細書において定義されるように、「シーム」は、単調であり、かつ連結された画素のパスであって、画像の上端から反対側の下端まで延びるか、または代替的には左端から反対側の右端まで延びる。ビデオ、すなわち画像の時間シーケンスの場合、シームは、時間次元内の２Ｄ多様体とすることができる。１つのシームを除去または挿入することによって、画像のサイズは、水平方向、垂直方向、または時間次元において１画素だけ低減または増加される。所望のサイズの出力画像を生成するために、シームを繰り返し除去または挿入することができる。]
[0023] ビデオにおいて、フレームシーケンス内の２Ｄシーム（多様体）を決定する。出力画像のサイズを増加若しくは減少させるため、または入力画像内の特定の部分を除去してオブジェクト除去をもたらすために、シームを繰り返し適用することができる。入力画像のサイズは、シームの画素を複製し、サイズ変更された画素を任意選択で出力画像内に混合することによって増加させることができる。]
[0024] いくつかの実施の形態では、画像内のエネルギーは、画素強度、色、またはビデオの場合は、動きに関連付けられる。画像内のエネルギーは、エネルギー関数に従って求めることができる。本明細書において説明されるように、たとえば、エネルギー関数は、強度、輝度、色、明白な動き、および類像性（iconicity）の局所的な変化を含む、局所顕著性の測定値を考慮することができる。]
[0025] 本発明では、有向アークによって連結されるノードからなる格子グラフを構築する。入力画像内の画素毎に１つのノードが存在し、有向アークは、画素のエネルギーに基づいてコストを割り当てられる。下記でより詳細に説明されるように、無限のコストを有する有向アークを使用して、単調性制約条件および連結性制約条件を施行する。]
[0026] 代替的に、ビデオフレーム内の重要度が低い領域を検索する。これは、各フレームにおけるエネルギー関数を独立して評価し、次に、各画素位置において最大エネルギーをとることによって行われる。このエネルギーを使用して、全てのフレームをサイズ変更する。この静的方法によって決定されるシームを「静的」シームと呼ぶ。これは、これらのシームがフレーム間で経時的に変化しないためである。]
[0027] ２００７年３月６日にAvidan他によって出願され、これもMitsubishi Electric Research Laboratories社に譲渡された、本発明者らの以前の米国特許出願である、米国特許出願第１１／６８２，５２１号明細書「Method for Retargeting Images」において、動的プログラミングを使用して、入力画像から最小コストシームを除去した、コンテンツベースの画像再構成（retargeting）方法が説明されている。しかしながら、出力画像によっては、依然として厄介なアーチファクトを有していた。本発明者らは、これらのアーチファクトは、サイズ変更された出力画像のエネルギーに対する、シーム除去の影響を考慮しなかったために発生したと認識している。本発明者らの以前の研究では、シーム除去に起因する入力画像内のエネルギー、すなわち後方エネルギーの変化を最小にした。今回、本発明では、出力画像内のエネルギー、すなわち前方エネルギーの変化を最小にする。本発明者らの以前の方法は、ビデオをサイズ変更するのに実用的ではなかったことも本発明者らは認識している。]
[0028] 本発明は、これらの問題に、以前のような動的プログラミングの代わりに、多次元格子グラフに対する切断を使用して対処する。さらに、最小コストシームを除去する代わりに、ここでは、入力画像と比較されるときの、サイズ変更された出力画像におけるエネルギー変化を最小にする。]
[0029] 本発明では、入力ビデオを画像の３Ｄボリューム（時間的に配列されたフレームシーケンス）として扱い、シームカービングを、２Ｄ画像上の１Ｄシームから、３Ｄボリューム上の２Ｄ多様体に拡張する。多様体と各フレームとの共通部分は、フレーム上のシームを画定する。多様体は、サイズ変更された出力ビデオ内の空間アーチファクトおよび時間アーチファクトの双方を大幅に低減する前方エネルギー関数を使用して見つけられる。本発明では、３Ｄ時空間ボリュームを通じて２Ｄ連結多様体１０３を構築するため、Avidan他による画像サイズ変更に使用される動的プログラミング手法は可能でない。したがって、本発明による方法は、グラフ切断を使用する。]
[0030] しかしながら、従来のグラフ切断は、本発明による新規の単調性制約条件および連結性制約条件下で、常に有効なシームを画定するとは限らない。]
[0031] 本発明では、単調であり、かつ連結したシームを生成する新規なグラフ切断を定義する。これは、シームが幅１画素であり、シーム内の画素が連結されている、すなわち水平方向または垂直方向のいずれかにおいて直接隣接していることを意味する。この定義を使用して、本発明では、シームカービングをビデオに適用し、ビデオボリュームを通る、単調であり、かつ連結した２Ｄ多様体シームを画定する。ビデオをサイズ変更するための処理時間を減少させるマルチ解像度手法も説明する。]
[0032] さらに、顕著な空間コンテンツおよび時間コンテンツを、より良好に保護するシームカービング判断基準も定義する。これによって、本発明によるサイズ変更された画像およびビデオの視覚的品質が大幅に改良される。新たな判断基準は、従来技術におけるように除去または挿入されるシームのコストではなく、サイズ変更された画像におけるエネルギー変化を最小にする。]
[0033] 前方エネルギー変化の最小化
エネルギー変化を最小にする上記の判断基準は、以下のように表すことができる。]
[0034] ]
[0035] ただし、Ｅはエネルギー関数（たとえば画素単位の強度差）であり、ＩＩは入力画像であり、ＩＯは出力画像であり、Ｃｉは関連付けられるコストを有する画素のシームである。]
[0036] ビデオサイズ変更
シームカービングを使用するビデオサイズ変更によって課される問題は、手順上の問題、次元の問題、基本的な問題として特徴付けることができる。]
[0037] 手順上の問題は、Avidan他の従来技術の動的プログラミング方法を３Ｄビデオボリュームに直接拡張することができないということから起こる。]
[0038] 次元の問題は、ビデオの追加の時間次元から発生する。ビデオの追加の時間次元によって、空間アーチファクトが増加し、動きに関連するアーチファクトがもたらされる。]
[0039] 基本的な問題は、ビデオがフレームシーケンスであり、したがって、ビデオシーケンスのいかなる処理も、大量のデータを伴うということが原因である。たとえば、ビデオ全体に必要とされるデータをランダムアクセスメモリ内に格納することはできない。したがって、これらのデータは、ディスク上に格納され、出力フレームがレンダリングされる前に要求に応じてロードされる。]
[0040] 本発明では、これらの問題に対処し、サイズ低減およびサイズ拡張のようなビデオサイズ変更アプリケーション、対話型のサイズ操作のためのマルチサイズビデオ、ならびにオブジェクト除去を説明する。]
[0041] 操作方法
図１は、本発明の１つの実施の形態による方法のステップを示している。入力画像１０１、またはビデオの場合は画像シーケンス（フレーム）から格子グラフ１１１を構築する（１１０）。単一の画像の場合、格子グラフは（Ｘ，Ｙ）平面内で２次元であり、ビデオにおけるような画像シーケンスの場合、格子グラフは３次元ボリューム（Ｘ，Ｙ，Ｔ）である。] 図１
[0042] 格子グラフは、各画像内の画素毎に１つのノードを含む。格子グラフ内の隣接するノードは、有向アーク１１２によって連結されている。有向アークは、水平方向に前方および後方に、垂直方向に上および下に、ならびに対角線方向に後方に延びる。]
[0043] エネルギー関数Ｅ（ｆ）を使用して、格子グラフ１１１においてアーク１１２にコストを割り当てる（１２０）。入力画像に対してエネルギー関数を計算する。コストを使用してコスト行列またはコストマップ１２１を構築することができる。コスト行列またはコストマップ１２１は、画像内の大域エネルギーを実質的に反映する。１つの画像の場合、コストマップは（Ｘ，Ｙ）平面内にある。ビデオの場合、コストマップは（Ｘ，Ｔ）平面内または（Ｙ，Ｔ）平面内のいずれかにあり得る。隣接するノードを連結する有向アークにコストを割り当てる。好ましい実施の形態では、コストは、入力画像内の隣接する画素間の強度の勾配量に基づく。すなわち、コストは、隣接するノードを連結するアークに対して定義される。]
[0044] アークを、コストマップＭを使用してコスト関数１３２に従って切断する（４００）。切断部の一方の側に隣接するノードに対応する画素は、シームを形成する。各シーム内の画素の座標は、単調性制約条件および連結性制約条件を施行する。アークにおけるコストによって施行される制約条件については、下記でより詳細に説明する。]
[0045] 次に、シーム４００に従って、入力画像１０１をサイズ変更して（１４０）、出力画像１０４を生成する。これは、出力画像において、入力画像からの顕著な視覚的コンテンツを保持しながら、入力画像に対する出力画像のエネルギー変化を最小にするように行われる。サイズ変更によって画素を付加または除去することができる。次に、出力画像をレンダリングするか、格納するか、通信するか、またはさらに処理する（１５０）ことができる。]
[0046] 以下の方法を、静的カメラを用いて取得されるビデオに適用することができる。一般的なビデオに関しては、下記で説明されるグラフ切断ベースのシームによる方法を参照されたい。]
[0047] Ｎ個のフレームからなるビデオシーケンスにおいて、各フレームは、水平座標ｉ、垂直座標ｊ、時間ステップｔ（フレーム）の場合に、｛Ｉｔ（ｉ，ｊ）｝個の画素を有する、ただしｔ＝１〜Ｎである。１つの実施の形態では、エネルギー関数は、Ｌ１ノルムに基づく。Ｌ１ノルムの場合、２つの隣接する画素間のアークのコストは、それらの強度（エネルギー）の絶対差の合計である。Ｌ１ノルムは、直線距離、街区距離、またはマンハッタン距離としても既知である。]
[0048] 本発明では、空間Ｌ１ノルム勾配量エネルギーＥｓｐａｔｉａｌを、時間勾配量エネルギーＥｔｅｍｐｏｒａｌと結合して、以下のように時空間Ｌ１ノルム勾配量エネルギーＥｇｌｏｂａｌを生成する。]
[0049] ]
[0050] ただし、α∈［０，１］である。]
[0051] ビデオの場合、エネルギー測定は、空間Ｌ１ノルム勾配量エネルギーの、２Ｄへの最大（max）投射である。ただし、αは空間エネルギー寄与と時間エネルギー寄与とを平衡させるパラメータである。実際には、動きアーチファクトは、より目立つため、エネルギーを時間重要性にバイアスし、たとえばα＝０．３とする。本発明によるエネルギー計算においては控えめに、平均ではなく最大投影を使用する。]
[0052] 利点として、本発明による静的方法は、単純かつ高速である。本方法は、ビデオが固定カメラによって取得され、前景および背景が容易に特定されるときに良好な結果を与える。しかしながら、より複雑なシーンのビデオ、またはカメラが動いているか若しくは複数の動きが存在するビデオでは、本発明によるシームは時間にわたって動的に適合することができる。]
[0053] このために、本発明では、ビデオシームを、３Ｄビデオボリュームを通って「切断する」、時空間における連結された２Ｄ多様体として定義する。表面と各フレームとの共通部分は、フレーム内の１つのシームを画定する。このため、この多様体の１つのシームを各ビデオフレームから除去する。多様体は連結されているため、シームはビデオの時間的一貫性を保持する。]
[0054] グラフ切断を使用するシームカービング
まず、本発明によるシームカービングの一般的な定式化を、画像におけるグラフ切断問題として説明した。そして、次に、シームカービングをビデオに拡張する。この説明を単純にするために、画像内の垂直シームを検索する。水平シームの場合、全てのグラフ構造は同じであり、適切に９０度回転される。]
[0055] 図３Ａ〜図３Ｅに示すように、格子グラフ内のノードは、有向アークによって連結される。入力画像１０１から格子グラフを構築し、ここで全てのノード３０１が画素ｐｉ，ｊを表す。グラフ３０２内の直接隣接するノードは、アーク３０２によって連結される。図３Ａ〜図３Ｅを参照されたい。] 図３Ａ 図３Ｂ 図３Ｃ 図３Ｄ 図３Ｅ
[0056] 視覚的な終端ノードＳ（ソース）およびＴ（ターゲット）は、水平シームの場合、画像の左端列および右端列の画素に対応し、垂直シームの場合、上端行および下端行に対応するエッジノードに対応する全てのエッジノードに、無限の（∞）コストアークを連結することによってグラフ内に構築される。終端ノードは、グラフのエッジおよび画像における動かせない「アンカー」として機能する。]
[0057] 本明細書において定義されるように、切断部は、格子グラフの１つのエッジから、格子グラフの真向かいのエッジに延在する。このため、格子グラフにおけるソースからターゲットへの（Ｓ／Ｔ）切断、または単に「切断」Ｃ４００は、グラフ内のノード（およびノードによって表される対応する画素）を、ｓ∈Ｓかつｔ∈Ｔとなるように２つの別個のサブセットＳ３１１およびＴ３１２に分割することとして定義される。図３Ａ〜図３Ｅおよび図４（Ａ）〜（Ｃ）を参照されたい。効果的には、切断はノードを連結しているアークを通る。切断、および切断の一方の側に隣接するシームの除去（または挿入）の後、次に新たなアークおよびコストを用いて格子グラフを再連結することができ、新たなコストマップを計算することができる。] 図３Ａ 図３Ｂ 図３Ｃ 図３Ｄ 図３Ｅ 図４
[0058] 切断Ｃ＝｛Ｓ，Ｔ｝の総コストは、切断される個々のアーク（ｐ，ｑ）のコストの合計として定義される。ただし、ｐ∈Ｓかつｑ∈Ｔである。ここで、コストは、Avidan他による本発明者らの従来の研究におけるように画素ではなく、アークに割り当てられることに留意されたい。コストは前方に向けられた切断に関してのみ合計される。すなわち、後方向におけるアークの無限コストは、切断の総コストに影響を与えない。切断からシームを決定する（１３０）ために、切断の一方の側、たとえば上端エッジから下端エッジに延在する切断に関して切断部の左側に直接隣接する画素を選択する。]
[0059] グラフ切断は、既知である。グラフ理論において、切断は、グラフの頂点を２つのセットに分割することである。より正式には、Ｇ（Ｖ，Ｅ）がグラフを表すものとする。切断は、頂点Ｖを２つのセットＳおよびＴに分割することである。ｕ∈Ｓかつｖ∈Ｔ（または有向グラフの場合は、ｕ∈Ｔかつｖ∈Ｓ）の任意のエッジ（ｕ，ｖ）は、切断を横切っており、被切断エッジであるとされる。]
[0060] しかしながら、本発明による方法と従来のグラフ切断との間には、多数の決定的な違いが存在する。従来のグラフ切断は、コンテンツを意識した画像サイズ変更ではなく、テクスチャ統合のために使用されてきた。さらに、従来の格子グラフは、方向性を有しない非常に単純な４連結グラフである。図３Ａを参照されたい。このグラフは、本発明による単調性制約条件および連結性制約条件を満たさないため、本発明によるシームカービングに有効なシームを画定しない。] 図３Ａ
[0061] 単調性制約条件
シーム内の画素ｐの座標ｉおよびｊは、シームの選択された方向、たとえば、下式において単調増加しなくてはならない。]
[0062] ]
[0063] 連結性制約条件
シーム内の画素を表すノードは、隣接し、かつ１つのアークによって直接連結されなくてはならない。すなわち、上記の単調性制約条件において、ｎ＝１でなくてはならない。]
[0064] 単調性制約条件および連結性制約条件を組み合わせて、シームを厳密に幅１画素にし、該シームを画像の一方のエッジから画像の真向かいのエッジへ連続的に延在させることができる。]
[0065] したがって、結果としてのシームがこれらの制約条件を満たすことを補償する格子グラフを構築することが課題である。]
[0066] 画像のためのグラフ切断
本発明による格子グラフにおいて、各ノード（画素）Ｐｉ，ｊは、自身の複数の直接近傍に８連結される。Ｌ１ノルム勾配量エネルギーＥ１に続いて、アークのコストを、図３Ｅに示される水平方向または垂直方向のいずれかにおける、画像内のコストに対応する画素間の前方差分として以下のように定義する。] 図３Ｅ
[0067] ]
[0068] 図２は、海辺の滝の入力画像２０１、および様々なグラフ構築に関して該画像に対して切断された４つのシーム２０２を示している。４つのシームに対応する可能な分割３０１が、それぞれ図３Ａ〜図３Ｄに示されている。各シームは、垂直切断の真左にある画素からなる。水平切断の場合のシームは、切断の真下となる。] 図２ 図３Ａ 図３Ｂ 図３Ｃ 図３Ｄ
[0069] 図３Ａ〜３Ｄにおいて、画像サイズ変更の目的のための異なる複数の可能なグラフ構築が、画像内の４つの隣接する画素を表す４つのノードによって示されている。実際の格子グラフは、これらのグラフを画像全体上に敷きつめることによって構築される。] 図３Ａ 図３Ｂ 図３Ｃ 図３Ｄ
[0070] 図３Ａにおける従来のグラフによって、妥当なシームではない一般的なパスが生じる。一方で、図３Ｂのグラフによって、単調であるが区分的に連結されたシームが生じる。図３のグラフは、Avidan他によるシームカービングに類似している。しかしながら、本発明では、動的プログラミングの代わりに格子グラフを使用する。図３Ｄのグラフは、本発明の実施の形態による前方コスト関数を表す。図３Ｅは、本発明による格子グラフをより詳細に示す。] 図３Ａ 図３Ｂ 図３Ｄ 図３Ｅ
[0071] 切断４００に単調性制約条件を課すために、水平アーク、垂直アーク、対角アークの異なる方向に異なるコストを使用する。前方アークの場合、すなわちＳからＴへの方向において、下記で定義するように、コスト＋ＬＲ３２１、＋ＬＵ３２２、および−ＬＵ３２３を使用する。後方水平アークおよび後方対角アークの場合、無限（∞）コスト３２０を使用する。本発明による格子グラフにおいて、画像のエッジにおける画素を表すノード以外の各ノードは、最大１２個の有向アークによって８個の隣接するノードに連結されることができることに留意されたい。図３Ｅを参照されたい。] 図３Ｅ
[0072] 以下に、本発明によるグラフ構築の下で単調性制約条件が施行される理由を論証する。]
[0073] 本発明によるグラフ切断構築と、Avidan他による従来技術の動的プログラミング手法との間の主な違いは、Avidanは、切断のための画素が連結されるように明示的に制約しないことである。Avidanによるグラフ切断は、いくつかの連続した垂直（または垂直）アークを通り抜け、実際に、区分的に連結されたシームを生成する。]
[0074] 本発明者らは、空間連続性および時間連続性の双方を保持するとともに、視覚的アーチファクトを最小にするために、連続して連結されたシームが重要であると考える。本発明では、切断が連結されるように制約するために、無限コストを有する後方対角アーク４１５を使用する。]
[0075] シーム制約条件
本発明による格子グラフは、無限コストを有する水平後方アークを使用して単調性を施行する。これは、切断の定義および構築の後に直接続く。終端ノードＳは、画素の左端（エッジ）列内の全ての画素に連結されており、右端列の全ての画素が終端ノードＴに連結されているため、別個のサブセットＳおよびＴを生成するために、全ての行は、何らかの場所で切断されなくてはならない。]
[0076] 最適な切断は、各行（または列）を通り抜ける。格子グラフ内に行ｊが存在し、切断が行ｊ内を２回通ると想定する。実際に、切断は特定の行または列を奇数回切断しなくてはならない。行ｊ内の連続する２つの切断を検討する。]
[0077] ノード（画素）Ｐｉ，ｊはＳとラベル付けされ、ノードＰｉ＋１，ｊ〜Ｐｋー１，ｊはＴとラベル付けされ、ノードＰｋ，ｊはＳとラベル付けされる。しかしながら、これは、無限コストアークであるＰｋ，ｊ→Ｐｋ−１，ｊが切断に含まれなくてはならないことも意味する。図４（Ａ）〜（Ｃ）を参照されたい。これによって、この切断は無限コスト切断となり、最適性に反する。これは、該切断が格子のある列において水平アークのみを切断し、有限コスト切断を達成することが常に可能であるためである。] 図４
[0078] ソースノードＳが画像の左端列に連結され、ターゲットノードＴが右端列に連結される場合、切断の左側の全てのノードは、Ｓとラベル付けされ、切断の右側の全てのノードは、Ｔとラベル付けされる。グラフ切断が同様に連結されることを望む場合には、後進対角アークを使用する。上記と同じ議論によって、図４（Ａ）〜（Ｃ）に示すような連結性を論証することができる。] 図４
[0079] 本発明では無限コストを有する後方水平アークおよび後方対角アークを使用するため、本発明による格子グラフは、シーム制約条件を施行する。図４（Ａ）に示すように、水平後方無限アーク４０２は単調性を施行する。対角無限大アーク４１５は連結性を施行する。図４（Ｂ）に示すように、切断４００が複数の画素を左側にスキップするか、または図４（Ｃ）に示すように右側にスキップする場合、ソースノード（白）４１１からターゲットノード（黒）４１２への無限大コストを有する対角切断は切断されなくてはならない。] 図４
[0080] 実際に、垂直アークおよび水平アークのコストを組み合わせることによって、動的プログラミング法によって見つけられるシームと同等なシームを定義する切断を有するグラフを構築することができる。図３Ｃを参照されたい。] 図３Ｃ
[0081] たとえば、水平前方アークに以下のコスト
Ｃ１（ｉ，ｊ）＝∂ｘ（ｉ，ｊ）＋∂ｙ（ｉ，ｊ）
を割り当て（１２０）、垂直アークを全体的に除去する。]
[0082] このグラフ内の切断は、単調であり、かつ連結されている。切断は、水平前方アークのみを考慮し、残りの無限コストアークは、連結性制約条件を課し、切断されることができない。したがって、本発明によるコストは、シーム内の全ての画素に関する全てのコストＣ１（ｉ，ｊ）の合計でもある。]
[0083] したがって、画素に関して定義される任意のエネルギー関数を、前方水平アークのコストとして使用し、動的プログラミングに基づくシームカービングと同じ結果を達成することができる。さらに、顔検出またはユーザによって定義されるコストマスクのような高レベルの機能を、本発明によるグラフ構築のうちの任意のものにおいて使用することができる。本発明では、画素のコストを、画素の外へ延びる水平アークに単に加える。]
[0084] ビデオのためのグラフ切断
ビデオに対する拡張が図５に示されている。本発明では、ほとんど垂直の（または水平の）多様体５０１を検索し、ビデオボリューム内のＸ×Ｔ平面５０２を検討し、無限の連結性コストを有する後方対角アークを含む、静止画像のためのＸ×Ｙ平面と同じグラフ構築を使用する。] 図５
[0085] 水平の場合、全てのフレームに関してそれぞれ、ソースノードおよびターゲットノードを全ての左端ノード、右端ノード、または上端ノード、または下端ノードに関連付ける。３Ｄ領域において２Ｄ多様体に対して定義されるグラフ切断を使用して、３Ｄビデオボリュームをソースセットおよびターゲットセットに分割する。そのような切断は、時間においても単調である。これは、各フレーム内の水平制約条件が既に整っているためである。この切断は、空間および時間の双方において、ボリューム内で大域最適である。各フレームに限定されて、切断は、１Ｄの連結されたシームを画定する。]
[0086] フルビデオボリュームの場合、計算時間は、ノード数とグラフ内のアーク数を乗算したものに依拠し、これは画素数における二次方程式である。全ての画素がノードによって表されるグラフに対する最小の切断を解くことは実現可能でない。効率を上げてリアルタイム処理を可能にするために、格子グラフは、低い解像度から高い解像度まで、複数の解像度において構築される。]
[0087] 適切な最小の切断は、まず解像度が最も低いグラフに関して計算され、次により高い解像度において繰り返し精緻化される。粗大化は、グラフを空間的および時間的の双方でダウンサンプリングすることによって実施され、一方で、精緻化は、より粗いレベルにおいて計算された切断によってもたらされる狭帯域に関して、グラフ切断を計算することによって行われる。本発明の場合、帯域は、時空間ボリュームを切り取る「スリーブ」の形式をとる。]
[0088] シームカービングに対するグラフ切断手法によって、コンテンツを意識したサイズ変更の利点をビデオに拡張すること可能になる。しかしながら、単一コスト関数は、全てのケースにおいて適切に機能するとは限らない。したがって、コンテンツをより良好に保持するとともに、ビデオのためのサイズ変更を改良するコスト関数を提供する。]
[0089] 前方エネルギー
Avidan他による従来技術のサイズ変更によって生じるビデオフレーム内のアーチファクトは、静止画像においても見ることができる。アーチファクトは、従来技術によるサイズ変更が、サイズ変更された画像内に挿入されるエネルギー、すなわち前方エネルギーを無視して、入力画像から最も少量のコストを有するシームを除去するために生じる。挿入されるエネルギーは、画素を除去（または挿入）し、それによって以前は隣接していなかった画素が、シーム適用の後に隣接するようになることに起因する。このため、サイズ変更された画像におけるエネルギー変化は、各シーム除去とともに増加または減少し得る。図６を参照されたい。] 図６
[0090] 本発明の実施の形態によるグラフ切断の実施態様において、画像のコストは、もはや従来技術の画素の属性ではなく、グラフ内のアークの属性である。したがって、画像の総コストは、全ての切断の有限コストの合計であり、各シームのコストは、対応する切断Ｃのコストである。このため、ｉ番目のシームカービングサイズ変更後のエネルギー差分は、以下である。]
[0091] ]
[0092] ただし、ｔは時間（フレーム）を表し、Ｃはシームに対応する切断のコストを表す。]
[0093] エネルギー差分は、実際に、異なる複数のシーム除去に関して増加および減少し得る。本発明は、サイズ変更された画像におけるエネルギー変化を最小にする。]
[0094] 図６は、各シームが除去された後（水平軸）の出力画像における、実際の（正規化された）エネルギー変化ΔＥ（垂直軸）を示している。変化ΔＥの理由は、シームが除去（または挿入）された後、切断の右側（または下側）の画素が新たな隣接する画素を有することである。このため、エネルギーおよびコストが再計算される場合、これらは実際に増加または減少し得る。] 図６
[0095] したがって、最適なシームを選択するための判断基準を提供する。従来技術におけるように、最小コストシームを除去する前の後方の入力画像を注目するのとは対照的に、本発明による判断基準は、前方の出力画像を注目する。]
[0096] 各ステップにおいて、除去されるとき、シームが除去された後のサイズ変更された出力画像におけるエネルギー変化を最小にするシームを検索する。これらのシームは、従来技術におけるように該シームのコスト自体が最小である必要は必ずしもないシームである。]
[0097] まず、静止画像のためのエネルギー関数を説明し、次に、ビデオに対するコスト関数の拡張を説明した。連結されたシームの除去は、画素の局所近傍におけるエネルギーにしか影響を与えないため、除去（または挿入）される画素に隣接する画素の小さな局所領域を調べれば十分である。]
[0098] 特定の画素を除去することによってサイズ変更された画像のエネルギーを、該サイズ変更された画像において生成される新たな「画素境界」に起因するものと考える。切断境界における画素のエネルギーは、シームが除去（または挿入）された後に新たな隣接する画素となる画素間の前方エネルギー差分として測定される。]
[0099] 垂直シームに関して図７（Ａ）〜（Ｃ）に示すように、シームの方向、左、上（または下）、および右に依拠して、３つのケースが可能である。シームを除去した後、新たな近傍および新たな画素エッジ７０２が生成される。各ケースにおいて、コストは新たに生成された画素エッジにおける前方差分によって定義される。行ｉ−１において作成される新たなエッジは、前回の行画素のコストにおいて計上されていたことに留意されたい。] 図７
[0100] ３つの可能なケースのそれぞれについて、それぞれ以下のようにコストを定義する。]
[0101] ]
[0102] ただし、ＣＬは左コストであり、ＣＵは上コストであり、ＣＲは右コストである。図７（Ａ）〜（Ｃ）を参照されたい。] 図７
[0103] 累積コストマップＭ１２１においてこれらのコストを使用して、シームを決定する。垂直シームの場合、各コストＭ（ｉ，ｊ）は、以下の関数を使用して更新される。]
[0104] ]
[0105] ただし、Ｐ（ｉ，ｊ）は、高レベルのタスク、たとえば顔検出器またはユーザコストから得られる結果のような付加的ベースのコスト測定であり、本発明による前方コストに加えて使用することができる。]
[0106] グラフ切断における前方コスト
グラフ切断の前方コストを求めるために、アークコストが、３つの可能なシーム方向に従って特定の画素を除去することによって引き起こされるコストを定義するグラフを構築する。]
[0107] ３つの全てのケースにおいて、新たな水平画素境界ｐｉ，ｊ−１ｐｉ，ｊ＋１が生成される。これは、太線で示されるように、画素ｐｉ，ｊが除去されるためである。したがって、ｐｉ，ｊ−１およびｐｉ，ｊ＋１を表すノード間のグラフアークに、左近傍と右近傍との間のコスト差分３２１を以下のように割り当てる。]
[0108] ]
[0109] 上記で説明したようなシーム単調性制約条件を施行するために、ノードｐｉ，ｊ＋１およびｐｉ，ｊを、無限コストを有する後方アークと連結する。また、無限コストを有する対角後方アークを加え、連結性を保持する。]
[0110] 次に、新たな垂直画素エッジに起因するコストを計上する。図７（Ｂ）に示すような垂直シームステップの場合、新たな垂直エッジは存在せず、このためコストは一切挿入されない。ここで、切断部の左側の全てのノードは、Ｓとラベル付けされ、切断部の右側の全てのノードは、Ｔとラベル付けされている。] 図７
[0111] 定義によって、切断のコストは、Ｓとラベル付けされるノードからＴとラベル付けされるノードに向けられるアークしか考慮しない。したがって、図７（Ａ）に示すように、右に配向された切断部において上方向の垂直アークのみがカウントされ、図７（Ｃ）に示すように、左に配向された切断部において下方向の垂直アークのみがカウントされるということになる。したがって、画素ｐｉ，ｊおよびｐｉ−１，ｊ間の上方向の垂直アークに、左近傍および上近傍間のコスト差分３２２を以下のように割り当てる。] 図７
[0112] ]
[0113] そして、画素ｐｉ−１，ｊおよびｐｉ，ｊ間の下方向の垂直アークに、コスト差分３２３を以下のように割り当てる。]
[0114] ]
[0115] ただし、−ＬＵは、矢印の終点に対する左近傍と上近傍との間の差分を意味する。]
[0116] 図８（Ａ）〜図８（Ｂ）は、図８（Ａ）の入力画像からの、従来技術の後方コスト関数を使用するシーム除去と、本発明による前方エネルギー関数を使用するシーム除去との間の劇的な差異を示している。従来技術のよる出力画像図８（Ｂ）では、ベンチに座っている人物は著しく歪み、フェンスの支柱のうちの１本が大幅に細くなっている。図８（Ｃ）の出力画像では、これらのアーチファクトのうちのいずれも存在しない。] 図８
[0117] 図９（Ａ）および図９（Ｂ）は、対応するシームを示している。ここで、図９（Ｂ）では人物および支柱を通る切断がより少ない。これは、本発明の前方エネルギーシームがより良好であることを明白に示している。] 図９
[0118] 図１０（Ａ）および図１０（Ｂ）は、それぞれのコストマップを示している。これらは、顕著なコンテンツに起因するコストが、図１０（Ｂ）に示すように本発明のコストマップにおいてより良好に保持されていることを明白に示している。図１０（Ａ）に示すように、コストはベンチ上の全てのバーを横切る毎に増加する。これは、バーが画像内のエッジを画定しているためである。図１０（Ｂ）において、垂直シームは、出力画像におけるコストを大幅に増加させることなくバーを横断することができる。] 図１０
[0119] ビデオの場合、シーム方向に依拠して３Ｄビデオボリューム内のスライスを調べる。垂直シーム、すなわちＹ方向の場合、（Ｘ×Ｔ）次元上の全てのスライスとシームとの共通部分によって、その平面上のシームが作成される。したがって、全ての画素除去のコストを、該画素が除去されるときにビデオ内にもたらされる、時間方向においてフレーム間で生成される新たな時間画素エッジとして定義する。次に、空間Ｘ×Ｙ領域におけるような適切なコストを有する、グラフ内のノード間のアークおよび時間ステップ（フレーム）間のアークを生成する。]
[0120] 上記で説明したように、顕著性マップ、オブジェクト検出器、および手作業で挿入されたエネルギーのような他のエネルギー関数も、本発明によるサイズ変更とともに使用することができる。大きなエネルギーを有する画素をマーク付けすることによって、ユーザは、サイズ変更プロセス中に、ビデオの特定の部分を保護することができる。本発明による手法は、大域的であるため、ユーザは全てのフレームをマーク付けする必要はなく、ｋ個のフレーム毎に１回マーク付けすればよい。実際には、１０個のフレーム毎にマーク付けする。負のコストを供給することによって、ユーザは、たとえばオブジェクト除去のために、シームをビデオの所望の部分に誘引することができる。]
[0121] 本発明による前方エネルギー判断基準によって、画像またはビデオのコンテンツおよび構造が保持される。しかしながら、構造を施行することは、時によってコンテンツを犠牲にして成り立ち得る。たとえば、目立ったアーチファクト、すなわち挿入されるコストなしでサイズ変更され得る重要なオブジェクトは、サイズ変更中に危険にさらされる場合がある。そのようなケースでは、前方判断基準とコストＥ１とを組み合わせることが、より良好な結果を達成するのに役立ち得る。これは、コストＥ１がコンテンツをより良好に保護することができるためである。]
[0122] 本発明を特定の好ましい実施の形態を参照して説明してきたが、様々な他の適合および変更を本発明の精神および範囲内で行うことができることを理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内に入るような全ての変形および変更を包含することである。]

权利要求:

請求項1
画像をサイズ変更するための方法であって、格子グラフは、入力画像内の画素毎に１つのノードを含み、該格子グラフ内の隣接するノードは、アークによって連結され、各該アークは、有向であるとともにコストに関連付けられることで、入力画像から格子グラフを構築するステップと、コスト関数を使用して前記格子グラフの前記アークに切断を適用するステップと、画像のシーム内の画素は、前記切断の一方の側に直接隣接する、前記格子グラフ内のノードに対応し、前記画像のシーム内の前記画素の座標は、単調性制約条件および連結性制約条件を施行することで、前記切断から画素のシームを決定するステップと、出力画像を生成するために、前記入力画像と比較されるときの、前記出力画像内のエネルギー変化を最小にしながら、前記シームに従って前記入力画像をサイズ変更するステップとを含む方法。
請求項2
前記格子グラフは、画像の時間シーケンスから構築され、該格子グラフは、３次元であり、前記シームは、前記格子グラフの空間次元ｘおよびｙ、ならびに時間次元ｔにおいて多様体を形成する請求項１に記載の方法。
請求項3
前記エネルギーは、画素の強度に基づき、前記コストは、エネルギー関数によって求められる請求項２に記載の方法。
請求項4
前記エネルギー関数は、局所的な強度変化を考慮する請求項３に記載の方法。
請求項5
前記アークの前記コストを使用して、前記単調性制約条件および前記連結性制約条件を施行するステップをさらに含む請求項１に記載の方法。
請求項6
前記最小にすることは、以下のように表され、ただし、Ｅはエネルギー関数であり、ＩＩは入力画像であり、ＩＯは出力画像であり、Ｃｉは前記切断に関連付けられるコストを有する画素のシームである請求項１に記載の方法。
請求項7
前記出力画像をレンダリングするステップをさらに含む請求項１に記載の方法。
請求項8
前記エネルギーは、空間Ｌ１ノルム勾配量エネルギーＥｓｐａｔｉａｌを、時間勾配量エネルギーＥｔｅｍｐｏｒａｌと結合して、以下に従って時空間Ｌ１ノルム勾配量エネルギーＥｇｌｏｂａｌを生成し、ただし、Ｉｔ（ｉ，ｊ）は画素に対応し、ｔは時間を表し、パラメータα∈［０，１］は空間コスト寄与と時間コスト寄与とを平衡させる請求項１に記載の方法。
請求項9
前記格子グラフ内の各前記ノードは、無限コストを有するアークによって他のノードに連結される請求項１に記載の方法。
請求項10
複数のシームを決定するステップと、前記複数のシームに従って前記入力画像をサイズ変更するステップとをさらに含む請求項１に記載の方法。
請求項11
前記切断の総コストＣは、切断される前記アークの前記コストの合計である請求項１に記載の方法。
請求項12
前記シーム内の前記画素ｐの前記座標ｉおよびｊは、前記シームの選択された方向において単調増加し、［Ｐｉ，ｊ→Ｐｉ＋１，ｊ］、［Ｐｉ，ｊ→Ｐｉ，ｊ＋１］、または［Ｐｉ，ｊ→Ｐｉ＋１，ｊ＋１］に従って直接隣接する請求項１に記載の方法。
請求項13
前記単調性制約条件および前記連結性制約条件は、前記シームを厳密に幅１画素にし、該シームを前記入力画像の一方のエッジから該入力画像の真向かいのエッジへ連続的に延在させる請求項１に記載の方法。
請求項14
前記格子グラフを粗い解像度から精緻な解像度までの複数の解像度で構築するステップと、前記格子グラフ上の前記切断を最も低い解像度を用いて概算し、次に該切断をより高い解像度で精緻化するステップとをさらに含む請求項１に記載の方法。
請求項15
前記シーム内の前記画素は、前記入力画像から除去され、より小さな出力画像が生成される請求項１に記載の方法。
請求項16
前記シーム内の前記画素は、前記入力画像内で複製され、より大きな出力画像が生成される請求項１に記載の方法。
請求項17
前記切断のコストを最小にするステップをさらに含む請求項１に記載の方法。